package org.example.Soution002;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordInRectangle {
    public static void main(String[] args) {
        String s1 = "ABCCED";
        char[][] board = new char[][]{{'A', 'B', 'C','E'}, {'S', 'F', 'C','S'}, {'A', 'D', 'E','E'}};
        WordInRectangle obj = new WordInRectangle();
        System.out.println(obj.exist(board, s1));

    }

    public boolean exist(char[][] board, String word) {
        char[] wordArray = word.toCharArray();
        boolean[][] visited=new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(wordArray[0] == board[i][j]&&judgeIfExist(wordArray, 0, board, i, j,visited)){
                    return true;
                }
            }
        }
        return false;
    }


    public boolean judgeIfExist(char[] wordArray, int order, char[][] board, int r, int c,boolean[][] visited) {
        if (order ==wordArray.length) return true;
        int R = board.length;
        int C = board[0].length;
        if(r<0||r>=R||c<0||c>=C||visited[r][c]||board[r][c]!=wordArray[order]) return false;
        visited[r][c]=true;

        boolean found=judgeIfExist(wordArray,order+1,board,r-1,c,visited)
                ||judgeIfExist(wordArray,order+1,board,r,c-1,visited)
                ||judgeIfExist(wordArray,order+1,board,r,c+1,visited)
                ||judgeIfExist(wordArray,order+1,board,r+1,c,visited);
        visited[r][c]=false;
        return found;
    }
}
